'''
https://leetcode.cn/problems/last-stone-weight-ii/description/
'''
from functools import cache
from typing import List

class Solution:
    # 想像成，擂台赛
    # 分成两组人，一直对打
    #       血没了的那一方就换人，另一方血不会恢复
    #       一直对打直到一方没人，返回胜者那一方剩余的血量，或者两败俱伤
    # 这样理解的话，其实就是找到一个累加和 <= sumall // 2, 较弱的一方
    #         return sumall - 较弱的 - 较弱的（胜方损失的血量） = 胜方剩余的血量
    def lastStoneWeightII(self, stones: List[int]) -> int:
        n = len(stones)
        sumall = sum(stones)
        @cache
        def f(i, rest):
            if i == n:
                return 0
            r1 = f(i+1, rest)
            r2 = 0
            if rest - stones[i] >= 0:
                r2 = stones[i] + f(i+1, rest - stones[i])
            return max(r1, r2)
        weaker = f(0, sumall // 2)
        return sumall - weaker - weaker

    # 改dp 打表
    def lastStoneWeightII2(self, stones: List[int]) -> int:
        n = len(stones)
        sumall = sum(stones)
        target = sumall // 2
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        # 第一维度依赖后边的，第二维度依赖前边的
        for i in range(n-1, -1, -1):
            for rest in range(target + 1):
                dp[i][rest] = dp[i+1][rest]
                if rest - stones[i] >= 0:
                    dp[i][rest] = max(dp[i][rest], stones[i] + dp[i+1][rest - stones[i]])
        weaker = dp[0][target]
        return sumall - weaker - weaker